package leetcode_101_120;

import org.apache.commons.lang3.SerializationUtils;
import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class pathSum_113 {
    /**
     *  找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        /**
         * 想法类似上一题，加上实时路径即可
         * 1ms
         */
        if(root==null)
            return ans;
        function(root,0, targetSum);
        return ans;
    }

    List<List<Integer>> ans=new ArrayList<>(); //结果集

    List<Integer>path=new ArrayList<>(); //实时路径

    public void function(TreeNode root,int sum,int targetSum){
        sum += root.val;  //路径和

        path.add(root.val);//实时路径添加当前节点

        if (root.right == null && root.left == null) {  //到了叶子节点
            if (sum == targetSum){
                List<Integer> copy = new ArrayList<>(path);
                ans.add(copy);
            }
            return;
        }
        if(root.left!=null) {
            function(root.left, sum, targetSum);
            path.remove(path.size() - 1);  //去除尾部元素
        }
        if(root.right!=null) {
            function(root.right, sum, targetSum);
            path.remove(path.size() - 1);  //去除尾部元素
        }
    }
}
